package hyy_2022;

/**
 * 斐波拉契数列
 *  f(n) = f(n-1) + f(n-2) n > 1
 *  答案需要取模 10^9 (1000000007) , 计算初始结果为1000000008 , 返回结果1
 *
 *  0 1 1 2 3
 *
 */
public class _0805_Offer10_509_I_Fib {

    /**
     * 用递归解题会超出时间限制
     * 看官方题解,用动态规划解题,斐波拉契数列具有递推特性
     * @param n
     * @return f(n)
     */
    public int fib(int n) {
        final int MOD = 1000000007;
        if(n < 2) {
            return n;
        }
        int p = 0, q = 0, r = 1;
        while(n > 1) {
            p = q;
            q = r;
            r = (p + q) % MOD;
            n --;
        }
        return r;
    }
}
